package net.sf.nlp.segment;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SegGraph 
{
	private static final int MAX_FREQUENCE = 2079997;
	private final double SMOOTH_PARAM = 0.1;
	
	private Dictionary relationDict;
	private int bestN;
	private List<AtomicWord> atomicWords;
	private List<SegNode> segNodes;
	
	public SegGraph(Dictionary relationDict, List<AtomicWord> atomicWords, List<SegNode> segNodes, int bestN)
	{
		this.relationDict = relationDict;
		this.bestN = bestN;
		this.atomicWords = atomicWords;
		this.segNodes = segNodes;
		
		if (this.bestN < 1)
			this.bestN = 1;
	}
	
	public List<AtomicWord> getAtomicWords() {
		return atomicWords;
	}
	
	public List<List<SegNode>> calculateShortPath()
	{
		GraphState[] states = new GraphState[atomicWords.size()];
		
		for (SegNode segNode : segNodes)
		{
			int start = segNode.getStart();
			
			if (states[start] == null)
				states[start] = new GraphState(start);
			
			GraphStateItem item = new GraphStateItem(segNode);
			item.setPreviousItems(getPreviousStateItem(states, start));
			states[start].addGraphStateItem(item);
		}
		
		List<List<SegNode>> paths = findBestPath(states);
		
		return paths;
	}
	
	private List<GraphStateItem> getPreviousStateItem(GraphState[] states, int end)
	{
		List<GraphStateItem> previousItems = new ArrayList<GraphStateItem>();
		
		for (int i = 0; i < end; i++)
		{
			List<GraphStateItem> items = states[i].getItems();
			
			for (GraphStateItem item : items)
			{
				if (item.getSegNode().getEnd() == end - 1)
					previousItems.add(item);
			}
		}
		
		return previousItems;
	}
	
	private List<List<SegNode>> findBestPath(GraphState[] states)
	{
		for (int i = 1; i < states.length; i++)
		{
			List<GraphStateItem> items = states[i].getItems();
			
			for (GraphStateItem item : items)
			{
				calculateWeight(item);
				
				item.trimToBestN();
			}
		}
		
		List<List<SegNode>> paths = getPaths(states);
		return paths;
	}
	
	private void calculateWeight(GraphStateItem item)
	{
		List<GraphStateItem> previousItems = item.getPreviousItems();
		
		if (previousItems == null)
			return;
		
		List<BestItem> bestItems = new ArrayList<BestItem>();
		
		for (GraphStateItem previousItem : previousItems)
		{
			
			List<BestItem> previousBestItems = previousItem.getBestItems();
			
			if (previousBestItems == null)
			{
				double weight = calculateWeigth(item, previousItem);
				BestItem previousBestItem = new BestItem(previousItem, null, 0);
				BestItem bestItem = new BestItem(item, previousBestItem, weight);
				
				bestItems.add(bestItem);
			}
			else
			{
				for (BestItem previousBestItem : previousBestItems)
				{
					double weight = calculateWeigth(item, previousBestItem);
					BestItem bestItem = new BestItem(item, previousBestItem, weight);
					
					bestItems.add(bestItem);
				}
			}
		}
		
		item.setBestItems(bestItems);
	}
	
	private double calculateWeigth(GraphStateItem item, GraphStateItem previousItem)
	{
		double freq = previousItem.getSegNode().getValue();
		double relatedFreq = 0;
		
		if (previousItem.getSegNode().isCustomized() || item.getSegNode().isCustomized())
			relatedFreq = 10000;
		else
		{
			String words = previousItem.getSegNode().getAliasNodeWord() + "@" + item.getSegNode().getAliasNodeWord();
			List<WordItem> wordItems = relationDict.getWordItems(words);
			if (wordItems != null && wordItems.size() > 0)
				relatedFreq = wordItems.get(0).getFreq();
		}
		
		// 计算相临两个词之间的平滑值
		// -log{a*P(Ci-1)+(1-a)P(Ci|Ci-1)} Note 0<a<1
		double temp = (double) 1 / MAX_FREQUENCE;
		double weight = SMOOTH_PARAM * (1 + freq) / (MAX_FREQUENCE + 80000);
		weight += (1 - SMOOTH_PARAM) * ((1 - temp) * relatedFreq / (1 + freq) + temp);
		weight = -Math.log(weight);

		return weight;
	}
	
	private double calculateWeigth(GraphStateItem item, BestItem bestItem)
	{
		double weight = calculateWeigth(item, bestItem.getItem());
		
		weight = weight + bestItem.getWeight();
		
		return weight;
	}
	
	private List<List<SegNode>> getPaths(GraphState[] states)
	{
		List<List<SegNode>> paths = new ArrayList<List<SegNode>>();
		
		GraphStateItem item = states[states.length - 1].getItems().get(0); 
		
		for (BestItem bestItem : item.getBestItems())
		{
			List<SegNode> path = new ArrayList<SegNode>();
			
			do
			{
				path.add(0, bestItem.getItem().getSegNode().clone());
				
				bestItem = bestItem.getPreviousBestItem();
			}
			while (bestItem != null);
			
			
			paths.add(path);
		}
		
		return paths;
	}
	
	class GraphState
	{
		int atomicWordIndex;
		List<GraphStateItem> items = new ArrayList<GraphStateItem>();
		
		public GraphState(int atomicWordIndex)
		{
			this.atomicWordIndex = atomicWordIndex;
		}
		
		public int getAtomicWordIndex() {
			return atomicWordIndex;
		}

		public void setAtomicWordIndex(int atomicWordIndex) {
			this.atomicWordIndex = atomicWordIndex;
		}

		public List<GraphStateItem> getItems() {
			return items;
		}

		public void setItems(List<GraphStateItem> items) {
			this.items = items;
		}

		public void addGraphStateItem(GraphStateItem item)
		{
			items.add(item);
		}
	}
	
	class GraphStateItem
	{
		SegNode segNode;
		List<GraphStateItem> previousItems = null;
		List<BestItem> bestItems = null;
		
		public GraphStateItem(SegNode segNode)
		{
			this.segNode = segNode;
		}
		
		public SegNode getSegNode() {
			return segNode;
		}

		public void setSegNode(SegNode segNode) {
			this.segNode = segNode;
		}

		public List<GraphStateItem> getPreviousItems() {
			return previousItems;
		}

		public void setPreviousItems(List<GraphStateItem> previousItems) {
			this.previousItems = previousItems;
		}

		public List<BestItem> getBestItems() {
			return bestItems;
		}

		public void setBestItems(List<BestItem> bestItems) {
			this.bestItems = bestItems;
		}
		
		public void trimToBestN()
		{
			if (bestItems == null)
				return;
			
			Collections.sort(bestItems);
			
			if (bestItems.size() <= bestN)
				return;
			
			for (int i = bestItems.size() - 1; i >= bestN; i--)
				bestItems.remove(i);
		}
	}
	
	class BestItem implements Comparable<BestItem>
	{
		GraphStateItem item;
		BestItem previousBestItem;
		double weight;
		
		public BestItem(GraphStateItem item, BestItem previousBestItem, double weight)
		{
			this.item = item;
			this.previousBestItem = previousBestItem;
			this.weight = weight;
		}

		public GraphStateItem getItem() {
			return item;
		}

		public void setItem(GraphStateItem item) {
			this.item = item;
		}

		public BestItem getPreviousBestItem() {
			return previousBestItem;
		}

		public void setPreviousBestItem(BestItem previousBestItem) {
			this.previousBestItem = previousBestItem;
		}

		public double getWeight() {
			return weight;
		}

		public void setWeight(double weight) {
			this.weight = weight;
		}

		@Override
		public int compareTo(BestItem bestItem) 
		{
			return Double.valueOf(weight).compareTo(bestItem.getWeight());
		}
	}
	
}
